第六讲 凹规划

Author
Affiliation

范翻

中央财经大学(CCFD)

凹函数及其导数 I

对于\(\theta \in [0,1]\)而言,称\(F(x)\)是凹函数,当且仅当:

\[ \begin{aligned} F(x^a + & \theta (x^b - x^a)) = F(\theta x^b + (1 - \theta) x^a) \geq \\ & \theta F(x^b) + (1 - \theta) F(x^a) \end{aligned} \]

稍作变形有 \[ \frac{F(x^a + \theta (x^b - x^a)) - F(x^a)}{\theta} \geq F(x) \]

\(\theta \rightarrow 0\),如果\(F\)是可微的,那么上式左边会趋近于\(F_x(x^a)(x^b - x^a)\)(洛必达法则)。因此有 \[ F_x(x^a) \geq \frac{F(x^b) - F(x^a)}{x^b - x^a} \]

凹函数及其导数 II

\(x\)是一维的时候:

  • \(F_x(x^a)\)就是函数\(F(x)\)\(x^a\)处切线的斜率

  • \(\frac{F(x^b) - F(x^a)}{x^b - x^a}\)是函数\(F(x)\)在点\(x^a, x^b\)之间连线的斜率

  • 函数的凹性意味着切线位于函数曲线之上

凹规划(Concave Programming)的定义

凹规划是一类特殊的数学优化问题,其目标函数为凹函数,且约束条件定义的可行域为凸集。具体形式如下:

\[ \begin{aligned} \max_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \geq 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p, \\ & x \in X \subseteq \mathbb{R}^n, \end{aligned} \] 其中:

  • 目标函数 \(f(x)\)凹函数(若为最小化问题,则要求 \(f(x)\) 是凸函数)。

  • 不等式约束 \(g_i(x)\)凹函数(确保可行域 \(\{x \mid g_i(x) \geq 0\}\) 是凸集)。

  • 等式约束 \(h_j(x)\)仿射函数(即线性函数加常数,形如 \(h_j(x) = a_j^T x + b_j\))。

  • 集合约束 \(X\) 是凸集(如 \(\mathbb{R}^n\) 或某个凸多面体)。

最大值函数的性质

对于每组给定的外生参数\(c\),最优选择\(\bar{x}\)和最大值\(\bar{v} = F(\bar{x})\)都是\(c\)的函数。令\(X(c)\)表示最优选择函数,\(V(c)\)表示最大值函数:

  • \(V\)对于\(c\)是非减函数,意味着约束条件放松,最大值不可能下降(最多持平)

  • \(V\)是凹函数,换言之对于任意给定的两组投入要素\(c, c'\),以及\(\theta \in [0,1]\),最大值函数满足 \[ V(\theta c + (1 - \theta) c') \geq \theta V(c) + (1 - \theta) V(c') \]

凹性的证明 I

自然地,我们考虑\(\theta \bar{x} + (1 - \theta) \bar{x}'\)是否可以满足上述要求。

  • 对于每一个\(j\),约束条件\(G^j\)是凸的,意味着 \[ \begin{aligned} & G^{j}(\theta \bar{x} + (1 - \theta) \bar{x}') \\ & \leq \theta G^j(\bar{x}) + (1 - \theta)G^j(\bar{x}') \\ & \leq \theta c_i + (1 - \theta) c_i' \end{aligned} \]

  • 因此,\(\theta \bar{x} + (1 - \theta) \bar{x}'\)是约束条件\(G(x) \leq \theta c_i + (1 - \theta) c_i'\)下的一个可行选择

凹性的证明 II

  • 根据\(F\)的凹性有 \[ \begin{aligned} & F(\theta \bar{x} + (1 - \theta)\bar{x}') \\ & \geq \theta F(\bar{x}) + (1 - \theta) F(\bar{x}') \\ & \geq \theta \bar{v} + (1 - \theta) \bar{v}' \end{aligned} \]

  • 而最大值\(V(\theta c + (1 - \theta) c')\)代表着所有可行选择中最大的收入,换言之,一定有 \[ \begin{aligned} & V(\theta c + (1 - \theta) c') \\ & \geq F(\theta \bar{x} + (1 - \theta)\bar{x}') \\ & \geq \theta \bar{v} + (1 - \theta) \bar{v}' \end{aligned} \]

经济学含义

  • \(G\)为凸函数,排除了生产中的规模经济或专业化,确保了一个加权平均的产量能够通过相同权重的平均投入生产出来

  • \(F\)为凹函数,保证了由此产生的收入大于等于各个收入的对应加权平均值

凹规划中的值函数

分离性质

  • 集合A是所有满足\(v \leq V(c)\)的点\((c, v)\)的集合,意味着使用投入向量\(c\)进行生产,生产出的产品至少能带来\(v\)的收入

  • 在集合A中选择一点\((c^*, v^*)\),使得\(v^* = V(c^*)\),这必然是一个边界点

  • 集合B是所有满足\(c \leq c^*\)\(v \geq v^*\)的点\((c, v)\)的集合

分离超平面: \[ \epsilon v - \lambda c = b = \epsilon v^* - \lambda c^* \] 其中\(\epsilon\)是一个标量,\(\lambda\)是一个m维向量,且满足 \[ \epsilon v - \lambda c \begin{cases} \leq b, & \forall (c,v) \in A \\ \geq b, & \forall (c,v) \in B \end{cases} \]

约束规格

斯拉特条件

斯拉特条件:集合A至少存在一个内点\(x_0\)使得\(G(x_0) \ll c^*\),即\(x_0\)满足所有约束条件且严格不等式成立

证明思路:

  • 假设存在\(x_0\)满足所有约束严格不等式 - 当\(\epsilon = 0\)时推导矛盾

  • 得出结论\(\epsilon > 0\)

关键等式: \[ \lambda(G(x_0) - c^*) = \sum_{i=1}^m \lambda_i(G^i(x_0) - c_i^*) < 0 \]

影子价格

  • \(\epsilon = 1\),则\(\lambda\)解释为投入要素的影子价格

  • 最大值函数\(V\)的可微性导致\(\lambda = V_c(c^*)\)

  • \(V\)不可微时,存在双边不等式: \[ V_i^- \geq \lambda_i \geq V_i^+ \]

一般化的边际产品

选择变量

通过分离定理推导关键不等式: \[ F(\bar{x}) - \lambda G(\bar{x}) \leq V(c) - \lambda c \]

结合互补松弛条件:

  • 对于每个约束\(i\)\(\lambda_i[c_i - G^i(\bar{x})] = 0\)

  • 要么\(\lambda_i = 0\),要么\(G^i(\bar{x}) = c_i\)

凹规划的必要条件

\(\bar{x}\)是凹规划问题的最优解,存在向量\(\lambda\)满足:

  • \(\bar{x}\)在无约束下最大化\(F(x) - \lambda G(x)\)

  • \(\lambda \geq 0\)且满足互补松弛条件

  • 可微情形下的一阶条件: \[ F_{x}(\bar{x}) - \lambda G_{x}(\bar{x}) = 0 \]

凸规划的充分条件 I

\(\bar{x}\)满足:

  • 最大化\(F(x) - \lambda G(x)\)

  • 满足互补松弛条件

则对任意可行\(x\)有: \[ F(\bar{x}) \geq F(x) \]

利用凹函数性质: \[ [F(x) - \lambda G(x)] - [F(\bar{x}) - \lambda G(\bar{x})] \leq 0 \]

凹规划的充分条件 II

\(\bar{x}\)\(\lambda\)满足以下条件:

  • \(\bar{x}\)在无约束的情况下最大化了\(F(x) - \lambda G(x)\)

  • \(\lambda \geq 0\)\(G(\bar{x}) \leq c\)满足互补松弛条件

那么\(\bar{x}\)在约束\(G(x) \geq c\)下最大化\(F(x)\)。如果\((F - \lambda G)\)是凹函数,那么 \[ F(x) - \lambda G(x) \leq F(\bar{x}) -\lambda G(\bar{x}) \] 也意味着条件(i)成立。

拟凹规划 (\(F\)拟凹,\(G\)为线性函数)

如果\(F\)为拟凹函数,那么 \[ \begin{aligned} F((1 - \theta) x^a + \theta x^b) \geq \min(F(x^a), F(x^b)) \end{aligned} \]

假定\(F(x^b) \geq F(x^a)\),那么 \[ F(x^a + \theta(x^b - x^a)) \geq F(x^a) \]

将上式看作关于\(\theta\)的函数: \[ h(\theta) \geq h(0), \quad \forall \theta \in [0,1] \]

通过链式法则推导: \[ \begin{aligned} h'(\theta) &= F_x(x^a + \theta (x^b - x^a))(x^b - x^a) \\ h'(0) &= F_x(x^a)(x^b - x^a) \geq 0 \end{aligned} \]

拟凹规划 II

考虑在线性约束\(px \leq b\)下最大化\(F(x)\),最优解必要条件为: \[ F_x(\bar{x}) - \lambda p = 0 \]

充分性证明: 对任意满足\(F(x) > F(\bar{x}) \equiv \bar{v}\)\(x\),取\(x^a = \bar{x}\)\(x^b = x\),由拟凹性可得: \[ F_x(\bar{x})(x - \bar{x}) \geq 0 \]

拟凹规划 III

结合必要条件推导: \[ p(x - \bar{x}) \geq 0 \Rightarrow px \geq p\bar{x} \]

反证结论:

  • \(px = p\bar{x}\),则\(x\)在满足约束下得到更大\(F\),矛盾

  • 故必有\(px > p\bar{x}\),即\(x\)不可行